What is Prefix Sum
- In computer science, the prefix sum, (cumulative sum), is a second sequence of numbers
y0, y1, y2,…, the sums of prefixes (previous numbers) of the input sequence: 
y0 = x0
y1 = x0 + x1
y2 = x0 + x1+ x2
input numbers 1 2 3 4 5 6 ...
prefix sums 1 3 6 10 15 21 ...
Implement Prefix Sum
arr = [1,2,3,4,5]
curr_res = 0
res = []
for i in range(len(arr)):
curr_res += arr[i]
res.append(curr_res)
print(res)
Suffix sum is running the above loop in reverse order, resulting prefix sum starting from the end to the start.
Application of Prefix Sum
- Prefix sum is a technique we can use to speed certain algorithm implementations
- Using prefix (or suffix) sums allows us to calculate the total of any slice of the array very quickly=O(n).
- moreover, prefix sums are usually used in questions including
subarray sum with x condition- maximum sub-array sub
- Examples